package com.me.study.arithmeticAndDataStructure.sort;

import java.util.Arrays;

/**
 * 归并排序
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] nums = {8, 7, 5, 3};
        int[] after = sortArray(nums);       // 得到排序后的数组
        System.out.println(Arrays.toString(after)); // 打印输出得到数组
    }

    private static int[] sortArray(int[] nums) {
        int len = nums.length;
        int[] temp = new int[len];
        mergeSort(nums, 0, len - 1, temp);
        return nums;
    }

    /**
     * 递归函数对 nums[left...right]进行归并排序
     *
     * @param nums  原数组
     * @param left  左边的索引
     * @param right 右边记录索引位置
     * @param temp
     */
    private static void mergeSort(int[] nums, int left, int right, int[] temp) {
        if (left == right) {// 当拆分到数组当中只要一个值的时候，结束递归
            return;
        }
        int mid = (left + right) / 2;   // 找到下次要拆分的中间值
        mergeSort(nums, left, mid, temp);// 记录树左边的
        mergeSort(nums, mid + 1, right, temp);// 记录树右边的

        // 合并两个区间
        for (int i = left; i <= right; i++) {
            // temp就是辅助列表，新列表的需要排序的值就是从辅助列表中拿到的
            temp[i] = nums[i];
        }

        // 归并算法的合并逻辑
        // i 表示左侧集合最小元素的下标
        int i = left;
        // j 表示右侧集合最小元素的下标
        int j = mid + 1;

        // k 是下标，表示小的元素赋值给 nums[k]
        for (int k = left; k <= right; k++) {
            // 如果左集合下标越界了，说明 右集合剩余元素 都比 左集合 大。
            //      并且，因为 右集合是有序的，所以直接把 右集合的剩余元素 填充到 nums[k] 即可。
            // 又因为已经确定只需要填充右集合的剩余元素，因此无需比较大小
            if (i > mid) {
                nums[k] = temp[j];
                j++;
                continue;
            }
            // 如果右集合下标越界了，说明 左集合剩余元素 都比 右集合 大，所以直接把 左集合的剩余元素 填充到 nums[k] 即可。
            else if (j > right) {
                nums[k] = temp[i];
                i++;
                continue;
            }

            // 从两个集合选出最小的元素比较大小，小的赋值给 nums[k]
            if (temp[i] <= temp[j]) {
                nums[k] = temp[i];
                i++;
            }
            else {
                nums[k] = temp[j];
                j++;
            }
        }
    }

}
